package com.algrithom.dp;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class DpProblem {
    
    public static void main(String[] args){
        int[][] array = {{1,3,5,9},{8,1,3,4},{5,0,6,1},{8,8,4,0}};
        int[][] result = getMinLoc(array);
        System.out.println("Min loc is: " + result[result.length - 1][result[0].length - 1]);
        result = getMaxLoc(array);
        System.out.println("Max loc is: " + result[result.length - 1][result[0].length - 1]);
        
        System.out.println("Total loc count is: " + totalLocCount(2,2));
    }
    
    private static int[][] getMinLoc(int[][] array){
        int rowLen = array.length;
        int colLen = array[0].length;
        List<Integer> list = new ArrayList<>();
        int[][] result = new int[rowLen][colLen];
        for (int i = 0; i < rowLen; i++) {
            for (int j = 0; j < colLen; j++) {
                if (i == 0 && j == 0) {
                    result[i][j] = array[i][j];
                    list.add(result[i][j]);
                } else if (i == 0) {
                    result[i][j] = result[i][j - 1] + array[i][j];
                } else if (j == 0) {
                    result[i][j] = result[i - 1][j] + array[i][j];
                } else {
                    int temp = Math.min(result[i - 1][j],result[i][j - 1]);
                    result[i][j] = temp + array[i][j];
                }
            }
        }
        list.add(array[rowLen - 1][colLen - 1]);
        System.out.println("The loc is: " + list.stream().map(String::valueOf).collect(Collectors.joining(",")));
        return result;
    }
    
    private static int[][] getMaxLoc(int[][] array){
        int rowLen = array.length;
        int colLen = array.length;
        int[][] result = new int[rowLen][colLen];
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < rowLen; i++) {
            for (int j = 0; j < colLen; j++) {
                if (i == 0 && j == 0) {
                    result[i][j] = array[i][j];
                    list.add(result[i][j]);
                } else if (i == 0) {
                    result[i][j] = result[i][j - 1] + array[i][j];
                } else if (j == 0) {
                    result[i][j] = result[i - 1][j] + array[i][j];
                } else {
                    result[i][j] = Math.max(result[i - 1][j],result[i][j - 1]) + array[i][j];
                }
            }
        }
        for (int i = 1; i < rowLen; i++) {
            for (int j = 1; j < colLen; j++) {
                if (result[i - 1][j] > result[i][j - 1]) {
                    list.add(array[i][j - 1]);
                    i = i + 1;
                } else {
                    list.add(array[i - 1][j]);
                    j = j + 1;
                }
            }
        }
        System.out.println("The loc is: " + list.stream().map(String::valueOf).collect(Collectors.joining(",")));
        return result;
    }
    
    private static int totalLocCount(int m,int n){
        if (m == 0 && n == 0) {
            return 0;
        }
        if (m == 0 || n == 0) {
            return 1;
        }
        return totalLocCount(m - 1,n) + totalLocCount(m,n - 1);
    }
}
